package Graph.directGraph;


import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeMap;

//  无权图 支持 有向、无向
public class DirectGraph implements Cloneable {

    //节点数
    private int V;
    //边数
    private int E;
    //因为是 有权图，所有用TreeMap 是一个键值对 <顶点，权值>
    private TreeMap<Integer,Integer>[] adj;

    private boolean directed;

    //有向图构造方法
    public DirectGraph(String filename,boolean directed){

        this.directed = directed;

        File file = new File(filename);

        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) {
                throw new IllegalArgumentException("V must be non-negative");
            }
            adj = new TreeMap[V];
            for(int i = 0; i < V; i ++) {
                adj[i] = new TreeMap<>();
            }

            E = scanner.nextInt();
            if(E < 0) {
                throw new IllegalArgumentException("E must be non-negative");
            }

            for(int i = 0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);


                if(a == b) {
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if(adj[a].containsKey(b)) {
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }
                int c = scanner.nextInt();

                adj[a].put(b,c);
                if(!directed) {
                    adj[b].put(a,c);
                }

            }
        }
        catch(IOException e){
            e.printStackTrace();
        }
    }

    //无向图构造方法
    public DirectGraph(String filename){
        this(filename,false);
    }

    //true 表示有向图，，false 表示无向图
    public boolean isDirected(){
        return directed;
    }

    public void validateVertex(int v){
        if(v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + "is invalid");
        }
    }

    @Override
    protected Object clone() {
        //默认的clone 是浅拷贝，我们需要深拷贝。 深拷贝其实就是把现在这个Graph 整个对象的详细细节（比如图的具体构造 邻接边什么的）也拷贝进去
        try {
            DirectGraph clone = (DirectGraph)super.clone();
            //做Graph 的深拷贝           -----开始
            clone.adj = new TreeMap[V];
            for(int v=0;v<V;v++){
                clone.adj[v] = new TreeMap<>();
                //① 这种方法 性能比较差
                /*for(int w:adj[v].keySet()){
                    clone.adj[v].put(w,adj[v].get(w));
                }*/
                for(int w: adj[v].keySet()) {
                    clone.adj[v].put(w,adj[v].get(w));
                }
            }
            //做Graph 的深拷贝           -----结束
            return clone;
        }catch (CloneNotSupportedException e){
            e.printStackTrace();
        }
        //如果有异常直接返回 null
        return null;
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public boolean hasEdge(int v, int w){
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }

    public Iterable<Integer> adj(int v){
        validateVertex(v);
        //不能直接返回TreeMap ，因为TreeMap没有实现Iterable<Integer> 接口，而keySet()实现了，keySet()是TreeMap的key集合
        return adj[v].keySet();
    }

    /*public int degree(int v){
        return adj[v].size();
    }*/

    public int getWeight(int v,int w){
        return adj[v].get(w);
    }


    public void removeEdge(int v,int w){
        validateVertex(v);
        validateVertex(w);
        if(adj[v].containsKey(w)){
            E--;
        }

        //因为是一个无向图，所以两边都要删除
        adj[v].remove(w);
        if(!directed){
            adj[w].remove(v);
        }
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();

        sb.append(String.format("V = %d, E = %d, directed= %b\n", V, E, directed));
        for(int v = 0; v < V; v ++){
            sb.append(String.format("%d : ", v));
            for(int w : adj[v].keySet()) {
                sb.append(String.format("(%d,%d) ", w,adj[v].get(w)));
            }
            /*for(Map.Entry<Integer,Integer> entry:adj[v].entrySet()){
                sb.append(String.format("(%d,%d)",entry.getKey(),entry.getValue()));
            }*/
            sb.append('\n');
        }
        return sb.toString();
    }

    public static void main(String[] args){

        DirectGraph adjSet = new DirectGraph("wg.txt",true);
        System.out.print(adjSet);
    }
}
